The modern communications era has brought about a tremendous expansion of wireline and wireless networks. Computer networks, television networks, and telephony networks are experiencing an unprecedented technological expansion, fueled by consumer demand. Wireless and mobile networking technologies have addressed related consumer demands, while providing more flexibility and immediacy of information transfer.
Current and future networking technologies continue to facilitate ease of information transfer and convenience to users. Due to the now ubiquitous nature of electronic communication devices, people of all ages and education levels are utilizing electronic devices to communicate with other individuals or contacts, receive services and/or share information, media and other content. One area in which there is a demand to increase ease of information transfer relates to the delivery of mapping services to a mobile terminal of a user. The mapping service may provide map data and location data requested by media or communication applications of the mobile terminal.
Currently, map or location data provided by mapping services is typically stored in a geographical database. The geographical database may be able to store, query and manipulate geographic information and spatial data that may be optimized for two or three dimensions. The spatial data may be stored as vector data in the form of geometric data such as, for example, a point, line, polygon, etc. and may have an associated spatial reference system. In this regard, the spatial data may be associated with coordinates such as latitude and longitude coordinates corresponding with locations or objects in the real world. As an example of spatial data, consider a highway which may be depicted as a two-dimensional object that contains lines, points and polygons that may represent towns, streets and boundaries such as, counties, states, etc. A map of the highway is the visualization of geographic information. The data that indicates the locations (e.g., latitude and longitude) of these rendered objects may be the spatial data. As such, geographical databases may store geometry data associated with streets, highways, waterways, oceans, landmarks, railroads, administrative area boundaries, etc. It should be pointed out that geographical databases may include records to represent the locations of objects or places in the real world.
At present, existing systems may utilize map tiles in order to facilitate fast retrieval of geographic data from a geographic database. One such technique for rendering the map tiles is tessellation. In this regard, existing systems may utilize tessellation to store data for specific locations by dividing the data up by location and partitioning the world into tiles. In other words, the geometric data corresponding to the real world may be partitioned into tiles and then a tile index for accessing the geographic database may be created based on the tiles.
This technique may be beneficial for mapping systems because mapping systems typically retrieve data in tile units from a geographical database. While this approach may provide good performance for data retrieval with respect to mapping systems, it may also incur high overhead in computing storage costs and computing processing costs. As such, one drawback with this approach of geometric data retrieval is that it may result in heavy use of computing storage resources (e.g., disk and memory) and processing resources for tile indexes. For instance, geographical data corresponding to a map tile may be zoomed according to a zoom level. As such, given a zoom level z, the number of map tiles at zoom z is 4z. As an example, consider FIG. 1 relating to the tile system.
Referring to FIG. 1, at zoom level 0, the whole world may be covered by one tile (e.g., 4z=40=1). At zoom level 1, the single tile from zoom 0 is split into four (e.g., 4z=41=4). At zoom level 2, each of the four tiles from zoom 1 is further split into four (e.g., 4z=42=16), so on and so forth. In other words, to generate tiles for zoom level zi every tile in zoom level zi-1 may be split into four, as shown in FIG. 1. Hence, each tile at a given zoom level may be equivalent to a rectangular block of tiles at higher zoom levels. For instance, the single tile x=0, y=0 at zoom level 0 may be equivalent to all four tiles at zoom level 1. Similarly, the tile x=0, y=1 at zoom level 1 may be equivalent to the tiles x=0, y=2; x=1, y=2; x=0, y=3; x=1, y=3 at zoom level 2.
In a system with a maximum zoom level of 18, the number of tiles at zoom level 18 is 418, resulting in over 64 billion tiles. In an instance in which the size of a leaf index node may be four bytes (e.g., the size of an integer pointer address), then for a zoom of 18 tiles, the total size of the leaf index nodes alone is roughly 256 gigabyte (GB). This is a huge amount of space overhead especially in consideration of the size of the database itself. For instance, the Navteq™ Streets database for the United States has approximately 27 million records with a total disk space size of 11 GB.
To resolve the disk space issue, existing tile-indexing systems typically make tile size tradeoffs when indexing geographical data. Smaller tiles at higher zoom levels contain small amounts of geographical data per tile and hence have better selectivity for queries requesting map data. However, using smaller tiles in this manner typically requires large amounts of disk space to maintain the resulting indexes. For instance, smaller tiles may result in more segment traversals requiring more space to be used. On the other hand, larger tiles at lower zoom levels typically contain large amounts of geographical data per tile and thus may have worse selectivity for queries requesting map data than smaller tiles. However, larger tiles typically require smaller amounts of disk space to maintain the resulting indexes. For instance, at zoom level 9, the disk space for leaf index nodes is only about one megabyte (MB) but may result in poor performance for tile requests at zoom level 18, for instance, because the query for map data may typically return a large number of records as there are 218 (over 260,000 tiles) zoom 18 tiles contained in each zoom 9 tile.
In view of the foregoing drawbacks of existing tile-indexing systems, it may be beneficial to provide an alternative mechanism for accessing geographic databases via tiles that may utilize computing storage resources more efficiently for tile indexes with respect to geographic databases.